This invention relates in general to random number generators and more specifically to random number generators which use both digital and analog random number sources.
Random number generators are used for a variety of purposes such as cryptography. Correct use of cryptography depends on a statistically high quality source of random numbers. Unfortunately, conventional random number generators ("RNG") have disadvantages.
Simple random number generators use digital techniques to produce pseudorandom numbers. Pseudorandom numbers are substantially or highly random numbers which are produced by a digital process. Digital techniques can produce pseudorandom numbers which are deterministic because of their digital nature. In other words, two identical digital random number generators produce the same pseudorandom number when the digital input values are the same. Accordingly, digital techniques produce less than ideal results because the pseudorandom numbers are predictable.
A common digital technique for generating a random number is a linear congruential generator algorithm. This algorithm iterates to produce an output which is used as the seed for the next output. However, the sequence of random numbers produced by this technique is small and repeats after a relatively small number of distinct outputs. An orbit is defined herein as the number of outputs the digital random number generator produces until one output is the same as a previous output. As can be appreciated, a recursive algorithm will produce unique outputs in the orbit until an output is repeated. Once the first value repeats, the subsequent values will also be repeats. A repeating pattern is undesirable since it is predictable. This algorithm is found in most C programming language libraries.
To provide robust random numbers, conventional systems rely upon analog random number generators. Analog random number generators produce a stream of random numbers which do not have a periodic orbit like the digital random number generators. These analog random number generators typically convert a random analog voltage, such as noise, into a digital stream of random data. These circuits are typically separate integrated circuits which generate a stream of random numbers at a rate of 100 Kbits or less. However, these random number generation rates are inadequate for very high performance cryptography, where a large number of random bits is needed in a short period of time.
Analog random number generators are prone to failure. The lifetimes of analog random number generators are considerably less than the digital circuits which use the random numbers. As can be appreciated by those skilled in the art, failure of the analog random number generator can defeat effective cryptology. Additionally, the source of the analog voltage used to generate the random number is vulnerable to control by an attacker. Accordingly, there is a need for more reliable analog random number generators which are less vulnerable to attack.
Analog random number generators are typically located on a separate integrated circuit from the digital circuits which use the random numbers because digital semiconductor processes are generally incompatible with analog semiconductor processes. Digital integrated circuits typically have high gain and are optimized for fast CMOS switching. However, analog random number generators require linear analog characteristics to effectively amplify the source of the random voltage in order to randomly produce a digital data stream. Modifying the digital semiconductor process to create better analog characteristics is possible, but the digital circuit performance would be adversely affected. Accordingly, integrating an analog random number generator on the same integrated circuit is very difficult with conventional techniques.
Additionally, an analog random number generator located on an integrated circuit separate from the integrated circuit containing the digital cryptographic function is prone to attack. More specifically, the trace on the circuit board which carries the random number to the cryptographic function is vulnerable. For example, an attacker can manipulate or replace the signal from the analog random number generator. As those skilled in the art can appreciate, this attack would render the cryptographic algorithm and keys more easily determinable.
In summary, it is desirable to develop a random number generator which reliably produces random numbers at a high data rate. Additionally, the random number generator should accommodate integration with digital circuits on the same integrated circuit.